When multiple images or sequences of images have or are being captured using camera or video equipment, it may be desirable to monitor those images to determine their content.
For example, a search may be desired to locate a particular image within a collection of images. The search criteria may be for one or more of a particular person, event, object, action etc., or any combination thereof. However, a vast amount of images are being collected on a regular basis day by day and so the search time for searching libraries of images and/or the computing power required to perform the search may be prohibitive.
As a further example, it may be desirable to monitor the images of a surveillance system to determine whether the images contain particular content therein. The search criteria in this example may also include one or more of a particular person, event, object, action etc., or any combination thereof.
A Markov random field (MRF) is a probabilistic model that models interactions among states of a system. An MRF determines a value for each possible MRF state of the system as a function of so-called total potential functions; the values collectively define a probability distribution over all possible states of the system. With the capability of exploiting the state inter-dependencies, MRFs have been shown to have wide applicability across different fields including robotics, molecular biology, image processing, and computer vision in order to assist in finding states that most closely relate to a defined search criteria.
Finding a maximum a posteriori (MAP) state of an MRF is a key inference problem which aims to find a most probable state of the system (the so called MAP-MRF problem). Solving a MAP-MRF is equivalent to finding the state with an optimal total potential. A MAP state of an MRF is also known as a MAP solution.
Finding a MAP solution to an arbitrary MRF is known to be NP-hard, that is, no algorithm can guarantee performance better than exhaustively testing all possible states. Nevertheless, MRFs are useful for modelling complex systems because there are efficient algorithms that (i) find approximate solutions, (ii) solve restricted classes of MRFs such as MRFs with potential functions admitting sub-modularity condition, or MRFs with acyclic dependencies among pairs of random variables, and (iii) find an exact or near exact MAP solution while avoiding the worst case performance for real-world models.
Exact or near-exact MAP solutions for densely connected MRFs are highly desirable in some problem domains such as those in computer vision where fast processing of images and videos is needed.
One approach for solving a MAP-MRF problem is based on a general branch-and-bound method. In a general branch-and-bound method, an original state space is split into smaller and disjoint parts of the original state space; the split being based on an upper bound estimate of each part, called a part upper bound of that part. The tightness and computation time of a part upper bound is important for a branch-and-bound method to quickly find a MAP solution. One approach for producing a part upper bound is to use a linear programming method. However, linear programming methods are expensive and may only be optimal for the first split; subsequent splits would require either reapplying a linear programming method or being content with a less effective part upper bound.
Another approach for producing a part upper bound is to statically compute a part upper bound without exploiting the structure of the parts. Such a method leads to poor part upper bounds, which prevents the method from quickly finding a MAP solution.
Another method for solving an MAP-MRF problem is to use belief propagation based on linear programming relaxation and dual optimisation in order to iteratively find a near or exact MAP solution. This method may be useful when finding a MAP solution for a sparse MRF where there may not be many inter-dependencies among variables of the MRF. However this method is slow and inefficient for cyclic or densely connected MRFs.
Hence, there exists a need to efficiently find exact MAP solutions for densely connected MRFs, which are particularly important in the field of pattern recognition.